package com.wujunshen.algorithm.leetcode.dynamic.programming;

/**
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/8/11 15:44<br>
 */
public class 最大矩形 {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        if(n == 0) {
            return 0;
        }
        int m = matrix[0].length;
        int[][] matrix1 = new int[n][m];
        for(int i = 0;i < m;i++){
            if(matrix[0][i] == '1') {
                matrix1[0][i] = 1;
            }
        }
        for(int i = 1;i < n;i++){
            for(int j = 0;j < m;j++){
                if(matrix[i][j] == '1') {
                    matrix1[i][j] = matrix1[i - 1][j] + 1;
                }
            }
        }

        return xx(matrix1,n,m);
    }

    private int xx(int[][] matrix,int n,int m){
        int ans = 0;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(matrix[i][j] * m <= ans) {
                    continue;
                }
                if(matrix[i][j] != 0){
                    int count = 1;
                    for(int k = j + 1;k < m;k++){
                        if(matrix[i][k] < matrix[i][j]) {
                            break;
                        }
                        count++;
                    }
                    for(int k = j - 1;k >= 0;k--){
                        if(matrix[i][k] < matrix[i][j]) {
                            break;
                        }
                        count++;
                    }
                    ans = Math.max(ans, count * matrix[i][j]);
                }
            }
        }
        return ans;
    }
}
